% !TEX encoding = UTF-8 Unicode
\chapter{$P$-círculo de radio mínimo con centro en una línea de consulta}
\section{Nuestro problema}

Sea $P$ un conjunto de $n$ puntos en el plano representando a $n$ sensores y sea $L$ una línea recta representando la vía de un tren.
Consideremos una antena inalámbrica $\mathcal A$ montada sobre un tren que viaja a lo largo de la vía representada por $L$. El objetivo de la antena es emitir un mensaje durante el trayecto en el tren, de manera que todos los sensores lo reciban.

Por motivos de seguridad, la antena $\mathcal A$ puede enviar un único mensaje durante el recorrido del tren,
más aún buscaremos la potencia óptima de transmisión, no sólo para minimizar los costos, sino que además no queremos que el mensaje se difunda a una gran distancia, ya que podría ser interceptado y se podría hacer un mal uso de la información.

Nuestro objetivo será entonces el de encontrar el momento justo durante el recorrido para emitir el mensaje, de manera que cada uno de los $n$ sensores reciba el mensaje y la potencia utilizada sea la mínima posible.
Recordemos que la potencia asignada a nuestra antena define un radio de transmisión $r$ alrededor de la posición de $\mathcal A$, por ende al momento de la transmisión, 
todo sensor deberá estar a distancia a lo más $r$ de $\mathcal A$ para recibir el mensaje.

Recordemos que nuestra antena, junto con su radio de transmisión, se puede representar geométricamente por un círculo con centro en la posición de $\mathcal A$ y radio $r$. 
Por ende la solución a nuestro problema se puede ver geométricamente como el $P$-círculo de radio mínimo con centro sobre la recta $L$, ya que éste determina el lugar y la potencia óptimas de transmisión de la antena $\mathcal A$; ver Figura~\ref{F_Introduccion}.

\begin{figure}[htbp]
\begin{center}
\includegraphics[angle=0, width=.75\textwidth]{img/cap2/Introduccion.pdf}
\caption{\small El círculo $C_L$ y su centro $c_L$ sobre la línea de consulta $L$.}
\label{F_Introduccion}
\end{center}
\end{figure}

\newpage
Dada una línea recta $L$, definimos a $C_L$ como el $P$-círculo de radio mínimo con centro sobre la recta $L$ y a $c_L$ como su centro;
nuestro problema se traduce entonces en encontrar el centro y radio de $C_L$ de manera eficiente.

En este capítulo presentaremos una caracterización del punto $c_L$ y mostraremos la estrecha relación que guarda con el diagrama de Voronoi del punto más lejano de $P$.
Esto nos permitirá generar un algoritmo de tiempo lineal para determinar la ubicación de $c_L$ una vez calculado el diagrama de Voronoi.
Finalmente, consideraremos una variante del problema, en dónde el conjunto de puntos $P$ está fijo mientras la recta $L$ varía.
Propondremos entonces una estructura de datos sobre $\mathcal{V}(P)$ y un algoritmo que nos permitirán encontrar eficientemente al punto $c_L$ dada cualquier línea recta $L$.

\section{El $P$-círculo de radio mínimo con centro en $L$}
Sea $P$ un conjunto de $n$ puntos en el plano, tales que no existen cuatro puntos cocirculares,
y sea $L$ un línea recta.
Siendo que nuestro objetivo es encontrar el $P$-círculo de radio mínimo con centro sobre la recta $L$, 
podemos suponer que $P$ es un conjunto de puntos en posición convexa, 
ya que cualquier círculo que contenga al cierre convexo de $P$, 
contiene también a todos los puntos interiores del conjunto.

\begin{defi}
Dado un punto $p$ de $P$, denotamos por $p_\perp$ al punto definido por la proyección ortogonal de $p$ sobre la recta $L$.
\end{defi}

Sea $p_L$ el punto de $P$ más lejano a la recta $L$.
La siguiente observación caracteriza las tres ubicaciones posibles de $c_L$ en relación al diagrama de Voronoi del punto más lejano y se puede observar a detalle en la Figura~\ref{F_CasosC_L}. 

\begin{prop}
Se cumple uno de los siguientes casos:
\begin{enumerate}\label{CasosC_L}
\item\ $C_L$ pasa por un único punto $p$ de $P$, si y sólo si $p = p_L$ y $p_\perp$ está en el interior de $R(p_L)$, en cuyo caso $c_L = p_\perp$ es el centro de $C_L$.
\item\ $C_L$ pasa por dos puntos $p_0,p_1$ de $P$, 
si y sólo si $c_L$ es la intersección de $L$ con una arista $e$ de $\mathcal{V}(P)$, y $e$ está contenida en la bisectriz de $p_0,p_1$.
\item\ $C_L$ pasa por tres puntos de $P$, si y sólo si $c_L$ es un vértice de $\mathcal{V}(P)$ que se encuentra sobre la recta $L$.
\end{enumerate}
\end{prop}

\begin{proof}
El inciso $(2), (3)$ y el el regreso del inciso $(1)$ se siguen de la definición del diagrama de Voronoi del punto más lejano.
Sin embargo, la ida del inciso $(1)$ no es trivial y la prueba se muestra a continuación. 

Si $C_L$ pasa por un único punto $p$ de $P$, por definición $c_L$ pertenece al interior de la región de Voronoi $R(p)$.
Procedamos por contradicción y supongamos que $c_L\neq p_\perp$.
Por consiguiente el triángulo rectángulo $\triangle(pp_\perp c_L)$ tiene como hipotenusa al segmento $[p,c_L]$ que es un radio de $C_L$.
Ahora, como $c_L$ está en el interior de $R(p)$, existe una $\varepsilon> 0$, tal que si movemos a $c_L$ una $\varepsilon$ distancia sobre $L$ en la dirección de $p_\perp$, tendremos que $c_L$ sigue perteneciendo a $R(p)$ y la hipotenusa del triángulo $\triangle(pp_\perp c_L)$ se redujo. 
Con esto encontraríamos un $P$-círculo de radio menor que el de $C_L$ con centro en la recta $L$ lo cual es una contradicción.
Por lo tanto, si $c_L$ pertenece a $R(p)$, $c_L$ es la proyección ortogonal de $p$ sobre $L$.
Es decir que $C_L$ es el círculo con centro en $p_\perp$ y radio $d(p, L)$.
Es fácil ver ahora que $p$ tiene que ser $p_L$, ya que $d(p_L, L)\geq d(q, L)$ para todo $q\in P$.

\end{proof}

\begin{figure}[htbp]
\begin{center}
\includegraphics[angle=0, width=1.05\textwidth]{img/cap2/CasosCL.pdf}
\caption{\small Los tres casos de la Proposición~\ref{CasosC_L}. Se puede observar que la proyección ortogonal de $p_L$ sobre $L$ no siempre yace en el interior de $R(p_L)$.}
\label{F_CasosC_L}
\end{center}
\end{figure}


\pagebreak
La proposición siguiente nos da un criterio para determinar la ubicación de $c_L$.

\begin{prop}\label{CasoFacil}
Sea $p$ un punto de $P$ y sea $p_\perp$ la proyección ortogonal de $p$ sobre la línea recta $L$.
Si $p_\perp\in R(p)$, entonces $c_L = p_\perp$.
\end{prop}
\begin{proof}
Si $p_\perp\in R(p)$, entonces $C(p_\perp)$ es un $P$-círculo tal que su circunferencia pasa por $p$. 
Si tomamos cualquier otro punto $x\in L$, como el triángulo $\triangle xp_\perp p$ es rectángulo con hipotenusa $[x,p]$, entonces tenemos que $d(x,p) > d(p_\perp,p)$.
Por lo tanto $\rho(x)\geq d(x,p) \geq d(p_\perp,p) = \rho(p_\perp)$, para todo $x\in L$. Concluimos entonces que entre los puntos de $L$, $\rho$ alcanza su mínimo en $p_\perp$ por lo que $c_L = p_\perp$; la proposición se observa en la Figura~\ref{fig:OrtogonalProyection}.
\end{proof}

\begin{figure}[htbp]
\begin{center}
\includegraphics[angle=0, width=.43\textwidth]{img/cap2/OrtogonalProyection.pdf}
\caption{\small El punto $p_\perp$ es el mínimo de la función $\rho$ sobre la recta $L$.}
\label{fig:OrtogonalProyection}
\end{center}
\end{figure}

Presentamos a continuación una observación que será utilizada de manera recurrente a lo largo de este trabajo.

\begin{obs}\label{Corta en un solo punto a R(p)}
Si $p$ es un punto en el cierre convexo de $P$, 
entonces toda semirrecta con ápice $p$ 
corta en a lo más un punto a la frontera de $R(p)$.
\end{obs}
\begin{proof}
Sean $\ell_1,\ell_2$ las bisectrices de los dos segmentos que inciden en $p$ en el cierre convexo de $P$, note que $\ell_1$ y $\ell_2$ contienen a las dos semirrectas que forman parte de la frontera de $R(p)$.
Además, $\ell_1,\ell_2$ forman una doble cuña en el plano, dejando a $p$ en un cuadrante y a $R(p)$ en el opuesto. 
Por lo tanto, toda semirrecta con ápice $p$ corta en a lo más un punto a $\ell_i$, $i=1,2$, esto aunado a la convexidad de $R(p)$ nos permite concluir nuestro resultado; ver Figura~\ref{F_Corta en un solo punto a R(p)}.
\end{proof}

\begin{figure}[htbp]
\begin{center}
\includegraphics[angle=0, width=.6\textwidth]{img/cap2/CortaUnPuntoR(p).pdf}
\caption{\small La prueba de la observación~\ref{Corta en un solo punto a R(p)}.}
\label{F_Corta en un solo punto a R(p)}
\end{center}
\end{figure}

\subsection{Calculando el $P$-círculo de radio mínimo con centro sobre una línea recta}
Sea $P$ un conjunto de $n$ puntos en el plano, sea $L$ una línea recta y sea $p_L$ el punto de $P$ más lejano a la recta $L$.
Propondremos un algoritmo de tiempo lineal para encontrar la posición de $c_L$ 
una vez calculado el diagrama de Voronoi del punto más lejano de $P$.
Cabe resaltar que existe un algoritmo de tiempo lineal propuesto por Megiddo en ~\cite{LinearTimeAlgorithmsForLinearProgramming}, 
para encontrar al punto $c_L$ sin la necesidad de calcular el diagrama de Voronoi. 
Sin embargo, las variantes del problema que introduciremos en lo sucesivo utilizarán al diagrama de Voronoi como parte central.
Por consiguiente el algoritmo aquí propuesto, nos dará mucha intuición y herramientas que usaremos más adelante.

Como primer paso del algoritmo construimos el diagrama de Voronoi del punto más lejano de $P$. 
Si los puntos del conjunto $P$ están en posición general, podemos construir a $\mathcal{V}(P)$ en tiempo $O(n \log n)$.
Sin embargo, si conocemos el cierre convexo de $P$, entonces podemos construir a $\mathcal{V}(P)$ en tiempo $O(n)$~\cite{LinearVoronoiDiagramForConvexPolygon}.
Sin perdida de generalidad, supondremos de aquí en adelante que los puntos de $P$ están en posición convexa, 
ya que en el proceso de construcción del diagrama de Voronoi obtenemos el cierre convexo de $P$.

Recordemos que por la Proposición~\ref{CasosC_L}, 
tenemos tres casos posibles para la ubicación de $c_L$ en relación a $\mathcal{V}(P)$.
En el primero $c_L$ pertenece al interior de la región de Voronoi de $p_L$, 
mientras que en el segundo y tercero $c_L$ yace sobre una arista del árbol $\mathcal{V}(P)$.
El algoritmo propuesto consta de dos fases. 
En la primera llevamos a cabo un proceso de evaluación de tiempo $O(\log n)$ para determinar si $c_L$ pertenece al interior de la región de Voronoi de $p_L$. 
Si $c_L$ pertence a $R(p_L)$, entonces gracias a la Proposición~\ref{CasosC_L} podemos garantizar que el punto $c_L$ está definido por la proyección ortogonal de $p_L$ sobre la recta $L$.
De lo contrario, en una segunda fase, el algoritmo revisará cada arista de $\mathcal{V}(P)$ hasta encontrar aquella que contenga a $c_L$. 

El proceso de evaluación de la primera fase se describe detalladamente a continuación.

\begin{alg}\label{TestCasoFacil}
Dado un punto $p\in P$.
Algoritmo para determinar si $c_L$ pertenece o no al interior de la región $R(p)$.
\end{alg}

Recordemos que $p_\perp$ denota el punto definido por la proyección ortogonal de $p$ sobre la recta $L$.
Revisaremos si $p_\perp$ se encuentra dentro de $R(p)$, ya que de ser así, la Proposición~\ref{CasoFacil} nos garantiza que $c_L = p_\perp$.

Sea $L_\perp$ la línea recta que contiene a los puntos $p, p_\perp$ y 
sea $s$ el punto de intersección de la frontera de $R(p)$ con $L_\perp$, si éste existe.
Note que podemos calcular a $s$ en tiempo $O(\log n)$ ya que $R(p)$ es un polígono convexo,
note también que $p_\perp$ está en el interior de $R(p)$, si y sólo si el punto $s$ está entre $p$ y $p_\perp$ sobre la recta $L_\perp$.

Si $p_\perp$ yace dentro de $R(p)$, entonces reportamos que $c_L = p_\perp$, 
de lo contrario concluimos que $c_L$ no pertenece a $R(p)$.

\begin{figure}[htbp]
\begin{center}
\includegraphics[angle=0, width=1\textwidth]{img/cap2/TestCasoFacil.pdf}
\caption{\small El accionar del Algoritmo~\ref{TestCasoFacil} sobre el punto $p_L$.}
\label{F_TestCasoFacil}
\end{center}
\end{figure}
\bigskip
\bigskip

\newpage

Note que podemos encontrar a $p_L$ en tiempo logarítmico llevando a cabo una búsqueda binaria sobre los vértices del cierre convexo de $P$, por lo que podemos aplicar el Algoritmo~\ref{TestCasoFacil} a $p_L$ y obtener en tiempo logarítmico uno de los dos siguientes casos.

Si encontramos a $c_L$ dentro de $R(p_L)$, 
entonces terminamos y reportamos al círculo con centro en $c_L$ y radio $d(c_L, p_L)$.
De lo contrario $c_L$ pertenece a una arista de $\mathcal{V}(P)$ y  
como el Lema~\ref{SizeVoronoi} garantiza que el número de intersecciones de $\mathcal{V}(P)$ con la recta $L$ es lineal, 
podemos revisar cada intersección y quedarnos con aquella que tenga el mínimo valor bajo la función $\rho$. El algoritmo se explica a detalle a continuación.

Sea $e$ una arista de $\mathcal{V}(P)$ contenida en la bisectriz de los puntos $p_0,p_1$ de $P$ y sea $x_e$  la intersección de $e$ con la recta $L$ si ésta existe.
Como supusimos que $e$ tiene apuntadores tanto a $p_0$ como a $p_1$, 
entonces en tiempo constante podemos determinar el valor de $\rho(x_e) = d(x_e,p_0) = d(x_e,p_1)$.

Ejecutando esta rutina de tiempo $O(1)$ en cada arista de $\mathcal{V}(P)$, 
podemos encontrar una arista $a$ de $\mathcal{V}(P)$, tal que $\rho(x_a) = \min\{\rho(x_e): e\in \mathcal{V}(P)\}$.
Claramente $c_L = x_a$, por lo que el algoritmo termina en tiempo $O(n)$ después de haber calculado el diagrama de Voronoi  del punto más lejano de $P$.

\newpage
\section{Encontrando a $C_L$ mediante consultas dinámicas}

Sea $P$ un conjunto de $n$ puntos en el plano.
Proponemos una nueva variante al problema en la cual nos permitimos realizar un preprocesado sobre el conjunto $P$, de manera que podamos responder a la siguiente consulta eficientemente:

Dada una línea recta $L$, encontrar el $P$-círculo de radio mínimo con centro sobre la recta $L$.

Note que la diferencia principal con el caso estático mostrado en la sección anterior, 
es que ahora $P$ es un conjunto de puntos fijo mientras que $L$ varía en cada consulta.
Podemos encontrar varios artículos en la literatura que abordan este problema, 
el primero fue presentado por Das, Karmakar, Nandy y Roy, quienes
propusieron un algoritmo con tiempo de preprocesado $O(n\log n)$ y  espacio lineal que responde a las consultas en tiempo $O(\log ^2 n)$~\cite{ConstrainedMinimumEnclosingCircleWithCenterOnAQueryLineSegment}.
Posteriormente Das, Karmakar y Roy mejoraron el tiempo de la consulta al óptimo $O(\log n)$, sin embargo aumentaron el espacio y preprocesado a $O(n^2)$~\cite{FastEnclosingCircle}.
En este capítulo presentamos un nuevo algoritmo para responder a la consulta en el tiempo óptimo $O(\log n)$, utilizando un preprocesado de tiempo $O(n \log n)$ y espacio $O(n)$.
Aunque cabe mencionar que Bose, Langerman y Roy estudiaron el mismo problema en~\cite{SmallestEnclosingCircleWithCenterOnQueryLine}. 
Ellos propusieron un algoritmo y estructura de datos completamente distintos, 
obteniendo el mismo tiempo de preprocesado y de consulta que nosotros.

\subsection{Esquema del algoritmo}
Retomando la construcción del punto $p_L$ y el accionar del Algoritmo~\ref{TestCasoFacil} descrito en la sección anterior,
podemos determinar, en tiempo $O(\log n)$, si $c_L$ pertenece al interior de la región de Voronoi de $p_L$ o yace en una de las aristas de $\mathcal{V}(P)$.
Como en el primer caso el Algoritmo~\ref{TestCasoFacil} resuelve le problema al reportar al punto $c_L$, 
supondremos de aquí en adelante que $c_L$ yace sobre una arista del árbol $\mathcal{V}(P)$.
Nuestro objetivo es entonces el de encontrar esta arista,
sin tener que probar todas las aristas de $\mathcal{V}(P)$.

Dada una línea recta $K$, sea $p_K$ el punto de $P$ más lejano a  $K$ y sea $c_K$ el centro del $P$-círculo de radio mínimo con centro sobre la recta $K$.
Definimos también a $p^*$ como el punto de $P$ más lejano a $L$, que se encuentre en el semiplano inducido por $L$ que contiene a $c_P$; ver Figura~\ref{fig:pEstrellaDefinicion}. 
Note que $p^*$ no necesariamente es el punto de $P$ más lejano a $L$ como se observa en la figura, aunque en muchos de los casos $p_L$ y $p^*$ coincidirán.

\begin{figure}[htbp]
\begin{center}
\includegraphics[angle=0, width=.6\textwidth]{img/cap2/pEstrellaDefinicion.pdf}
\caption{\small Podemos ver que $p^*$ puede ser diferente de $p_L$ si $c_P$ y $p_L$ están en distintos semiplanos inducidos por $L$.}
\label{fig:pEstrellaDefinicion}
\end{center}
\end{figure}

\pagebreak
Los pasos a seguir por nuestro algoritmo se describen a grandes rasgos a continuación.
\begin{enumerate}
\item Primero encontraremos una línea recta $M$ paralela a $L$, tal que \linebreak$c_M\in R(p^*)$; ver Figura~\ref{F_Existe L' paralela a L}. Además pediremos que $c_M$ y $c_P$ se encuentren en distintos semiplanos inducidos por $L$.
\item Como $c_M\in R(p^*)$, usando el Algoritmo~\ref{TestCasoFacil}, podemos calcular la posición del punto $c_{M}$ en tiempo logarítmico.
\item Finalmente tomaremos una línea recta $K$ paralela a $L$, y la trasladaremos continuamente desde la posición de la recta $M$ hasta la posición de la recta $L$, sin perder la ubicación del punto $c_K$ en el proceso.
\end{enumerate}

En las siguiente sección daremos las ideas y justificaciones formales detrás de la intuición que acabamos de presentar.


\begin{figure}[htbp]
\begin{center}
\includegraphics[angle=0, width=.9\textwidth]{img/cap2/IdeaAlgoritmo.pdf}
\caption{\small Podemos ver la existencia una recta $M$, paralela a $L$, suficientemente lejos de $p^*$, para la cual $c_{M}$ es la proyección ortogonal de $p^*$ sobre $M$.}
\label{F_Existe L' paralela a L}
\end{center}
\end{figure}

\newpage
\subsection{$c_L$ y las trayectorias sobre el árbol $\mathcal{V}(P)$}
Sea $P$ un conjunto de $n$ puntos en el plano y sea $L$ una línea recta.

\begin{prop}\label{Existe L' paralela a L}
Si $p^*$ es el punto de $P$ más lejano a $L$ en el semiplano inducido por $L$ que contiene a $c_P$, entonces
existe una línea recta $M$ paralela a $L$, tal que $c_{M}$ es  la proyección ortogonal de $p^*$ sobre $M$, $c_{M}\in R(p^*)$ y $d(M, p^*) \geq d(L, p^*)$.
\end{prop}
\begin{proof}
Sea $L_\perp$ la línea recta perpendicular a $L$ que pasa por $p^*$  y sea $\lambda$ la semirrecta contenida en $L_\perp$ con ápice $p^*$ que corta a $L$; ver Figura~\ref{F_Existe L' paralela a L}.

Definimos la función $c_{\lambda}:\mathbb{R^+}\to \lambda$, tal que $c_{\lambda}(x)$ es el punto sobre $\lambda$ a distancia $x$ de $p^*$. 
Para todo $x\in \mathbb{R^+}$, denotamos por $C_\lambda(x)$ al círculo con centro en $c_{\lambda}(x)$ y radio $x$.
Es fácil ver que si $x$ tiende a infinito, entonces $C_\lambda(x)$ tiende a una línea recta $\ell$ paralela a $L$ que contiene a $p^*$.
Más aún, $\ell$ es una recta soporte del cierre convexo de $P$, por ende podemos ver a $\ell$ como un $P$-círculo con centro en el infinito.

Concluimos entonces que debe existir $x_0>0$ tal que $C_\lambda(x_0)$ sea un $P$-círculo, por lo tanto, como $p^*$ está en la circunferencia de $C_\lambda(x_0)$, tenemos que $c_{\lambda}(x_0)\in R(p^*)$.
Ahora bien, si definimos a $M$ como la recta paralela a $L$ que pasa por $c_{\lambda}(x_0)$, entonces $c_{M} = c_{\lambda}(x_0)$ por la Proposición~\ref{CasoFacil}; ver Figura~\ref{F_Existe L' paralela a L}. Además, es claro por construcción que $d(M, p^*) \geq d(L, p^*)$.
\end{proof}

\pagebreak
La siguiente definición nos permitirá trabajar con las trayectorias dentro del árbol $\mathcal{V}(P)$ de manera más intuitiva.

\begin{defi}
Sea $x$ un punto sobre una arista de $\mathcal{V}(P)$. Denotamos por $\mathcal T_x$ a la trayectoria contenida en $\mathcal{V}(P)$ que une a $c_P$ con el punto $x$.
\end{defi}

Sea $M$ la línea recta paralela a $L$ existente como consecuencia de la Proposición~\ref{Existe L' paralela a L}, y supongamos sin pérdida de generalidad que $M$ es la línea recta más cercana a $p^*$ con estas propiedades.
Es claro entonces que $c_{M}$ es un punto sobre la frontera de $R(p^*)$; 
ver Figura~\ref{F_Existe L' paralela a L}.
La idea es entonces regresar la recta $M$ hasta $L$ sin perder la ubicación de $c_M$ en el proceso, para lo cual encontraremos útil el siguiente teorema.


\begin{lma}\label{c_K esta en la T_c_M para toda K}
Si $K$ es una recta paralela a $L$ tal que
$$d(M,p^*)\geq d(K,p^*) \geq d(L,p^*),$$
entonces $c_{K}$ es un punto sobre una arista de $\mathcal T_{c_M}$.
\end{lma}
\begin{proof}
Denotaremos por $\tau$ a la curva continua en el plano, formada por la unión de las aristas de la trayectoria $\mathcal T_{c_{M}}$.
Note que si movemos continuamente a la recta $K$, desde $M$ hasta $L$, sin modificar su pendiente, 
entonces el punto $c_{K}$ se mueve describiendo una curva continua $\gamma$. 
Afirmamos que $\gamma$ está contenida en la curva $\tau$.

Procedemos por contradicción.
Supongamos que existe una línea recta $K_{0}$, tal que $d(M,p^*)\geq d(K_{0},p^*) \geq d(L,p^*)$ y $c_{K_{0}}\notin \tau$. 
Como $c_{M}\in\gamma\cap \tau$,
entonces podemos definir a $K'$ como la paralela a $L$ más cercana a $p^*$, 
tal que $c_{K'}\in \gamma\cap \tau$ y $d(M,p^*)\geq d(K',p^*) > d(K_{0},p^*)$.

Sea $\varepsilon>0$ y sea $K_ \varepsilon $ la línea recta que representa a $K'$ desplazada hacia $p^*$ una $\varepsilon$ distancia. 
Es claro que $c_{K_ \varepsilon}\notin \tau$, por consiguiente está en el interior de una región de Voronoi $R(q)$, para algún punto $q$ de $P$.
Sin embargo, por el inciso $(1)$ de la Proposición~\ref{CasosC_L}, 
tenemos que esto ocurre si y sólo si $q$ es el punto más lejano de $K_ \varepsilon $.
Por lo tanto forzosamente $q=p^*$; más aún, $c_{K_ \varepsilon}$ tiene que ser la proyección de $p^*$ sobre $K_ \varepsilon$ y $c_{K_ \varepsilon}\in R(p^*)$. 
Note que además $d(K_ \varepsilon,p^*)< d(M,p^*)$, lo cual es una contradicción, 
pues $M$ era la recta con estas propiedades más cercana a $p^*$.

Por lo tanto, para toda línea recta $K$ paralela a $L$, tal que $$d(M,c)\geq d(K,c) \geq d(L,c),$$ se cumple que $c_{K}\in \tau$ y por ende $c_{K}$ pertenece a una arista de $\mathcal T_{c_{M}}$.
\end{proof} 


Sea $x$ un punto sobre una arista de $\mathcal{V}(P)$. 
En la Figura~\ref{F_LcortaEnVariosPuntos} podemos observar como la recta $L$ puede tener varias intersecciones con $\mathcal T_x$,
sin embargo, gracias al siguiente resultado podemos garantizar que la intersección de $\mathcal T_{c_M}$ con $L$ es única, lo cual será determinante en el algoritmo que propondremos más adelante.

\begin{figure}[htbp]
\begin{center}
\includegraphics[angle=0, width=1\textwidth]{img/cap2/LcortaEnVariosPuntos.pdf}
\caption{\small La trayectoria $\mathcal T_x$ corta en dos puntos a la recta $L$.}
\label{F_LcortaEnVariosPuntos}
\end{center}
\end{figure}


\begin{lma}\label{InterseccionUnicaConL}
La trayectoria $\mathcal T_{c_M}$ corta en un único punto a la recta $L$.
\end{lma}
\begin{proof}
Denotaremos por $\tau$ a la curva continua en el plano, formada por la unión de las aristas de la trayectoria $\mathcal T_{c_M}$.
Recordemos que si trasladamos a la recta $M$ hacia $p^*$ de manera continua, entonces $c_{M}$ describe una curva continua $\gamma$ en el plano.

Procedemos por contradicción, supongamos que $L$ corta a $\tau$ en al menos dos puntos.
Por construcción sabemos que $M$ corta en un sólo punto a $\tau$, por ende, entre $L$ y $M$ podemos definir una línea recta $K$ paralela a $L$, tal que $K$ sea la paralela más lejana a $p^*$ que corta en al menos dos puntos a $\tau$.
Note que cualquier recta $N$ paralela a $L$ tal que 
$d(M,p^*) \geq d(N,p^*) > d(K,p^*),$
corta en un sólo punto a $\tau$ y dicha intersección define al punto $c_{N}$; ver Figura~\ref{F_LCortaT_M}.

Sean $x_0, \ldots, x_m$ los puntos de intersección de $K$ con $\tau$, y supongamos que están ordenados de mayor a menor con respecto a su profundidad en el árbol $\mathcal{V}(P)$.
Recordemos que por el Teorema~\ref{monotonoia rho}, $c_K = x_m$, pues $\rho(x_m) \leq \rho(x_i)$, $i\in \{0, \ldots, m\}$. Sin embargo esto representa una discontinuidad de la curva $\gamma$, pues $x_0$ es un punto de acumulación de $\gamma$. Contradicción que viene de suponer que $L$ corta a $\tau$ en más de un punto.
\end{proof}

\begin{figure}[htbp]
\begin{center}
\includegraphics[angle=0, width=.95\textwidth]{img/cap2/LCortaT_M.pdf}
\caption{\small La prueba del Lema~\ref{InterseccionUnicaConL}.}
\label{F_LCortaT_M}
\end{center}
\end{figure}

\begin{tma}\label{c_L esta en la T_c_M}
Dada una línea recta $L$, si $M$ es la paralela a $L$ más cercana a $p^*$, 
existente como consecuencia de la Proposición~\ref{Existe L' paralela a L}, entonces $c_L$ es el único punto de intersección entre la trayectoria $\mathcal T_{c_M}$ y la recta $L$.
\end{tma}
\begin{proof}
Por definición, sabemos que $p^*$ y $c_P$ se encuentran en el mismo semiplano definido por $L$, por ende al construir a la recta $M$ alejándonos del punto $p^*$, 
garantizamos que la recta $M$ y el punto $c_P$ se encuentran en distintos semiplanos definidos por $L$.
Por consiguiente la trayectoria $\mathcal T_{c_M}$ corta a la recta $L$ y lo hace en un único punto gracias al Lema~\ref{InterseccionUnicaConL}.
Más aún, el Lemma~\ref{c_K esta en la T_c_M para toda K} garantiza que $c_L$ es exactamente el punto de intersección entre la trayectoria $\mathcal T_{c_M}$ y la recta $L$.
\end{proof}

\newpage
\subsection{Estructura de datos sobre $\mathcal{V}(P)$}\label{EstructuraDatos}
Gracias al Teorema~\ref{c_L esta en la T_c_M}, podemos garantizar que el punto $c_L$ está sobre una arista de $\mathcal T_{c_M}$. Sin embargo esta trayectoria podría ser, en principio, cualquier trayectoria contenida en $\mathcal{V}(P)$.
Nuestro objetivo será entonces desarrollar una estructura de datos, 
que nos permita hacer búsquedas eficientes sobre las aristas de cualquier trayectoria en el árbol $\mathcal{V}(P)$.


Describiremos una estructura de datos simple que requiere de tiempo y espacio $O(n\log n)$ para su construcción, y que permite realizar búsquedas binarias sobre cualquier trayectoria del árbol $\mathcal{V}(P)$ en tiempo $O(\log n)$.
Sin embargo, cabe destacar que existe otra estructura de datos más ingeniosa y compleja, propuesta por Roy, Karmakar, Das y Nandy~\cite{ConstrainedMinimumEnclosingCircleWithCenterOnAQueryLineSegment}, que requiere de tiempo y espacio $O(n)$ para su construcción, y que permite realizar búsquedas en el mismo tiempo de ejecución.

\begin{figure}[h]
\begin{center}
\includegraphics[angle=0, width=1\textwidth]{img/cap2/EstructuraDatosB_v.pdf}
\caption{\small La sub-estructura para los vértices $v_0, v_1$.}
\label{F_EstructuraDatosB_v}
\end{center}
\end{figure}

Para la construcción de la estructura de datos, supongamos que el árbol $\mathcal{V}(P)$ ya ha sido calculado; para mayor detalle revisar el Capítulo~\ref{Diagrama Voronoi}.
Realizaremos una Búsqueda en Profundidad (BP) sobre la gráfica $\mathcal{V}(P)$ partiendo del vértice raíz $c_P$. 
La única diferencia es que usaremos un arreglo de tamaño $n$ en vez de una pila durante la BP, haremos esto ya que necesitaremos acceso aleatorio a los elementos de la pila.


Es claro que cuando la BP alcance a un vértice $v$ a profundidad $\lambda$, 
la pila (emulada por un arreglo) constará exactamente de los $\lambda $ vértices de la trayectoria $\mathcal T_v$.
En ese momento asociaremos al vértice $v$ una sub-estructura $B_v$, que consiste de una arreglo de tamaño $\lceil \log \lambda \rceil$ con apuntadores a los elementos de la pila en las posiciones $\lceil \frac{\lambda}{2} \rceil, \lceil \frac{3\lambda}{4} \rceil, \lceil \frac{7\lambda}{8} \rceil, \ldots$.
Note que estos apuntadores corresponden exactamente a los vértices en $\mathcal T_v$ a profundidades $\lceil \frac{\lambda}{2} \rceil, \lceil \frac{3\lambda}{4} \rceil, \lceil \frac{7\lambda}{8} \rceil, \ldots$ en el árbol $\mathcal{V}(P)$; ver Figura~\ref{F_EstructuraDatosB_v}.

La construcción de la sub-estructura $B_v$ requiere entonces de tiempo y espacio $O(\log n)$, por lo que al asociar esta estructura a cada vértice de $\mathcal{V}(P)$ durante la BP, construiremos una estructura de datos de tamaño $O(n\log n)$.
Más aún, el tiempo requerido para construir esta estructura, incluyendo el tiempo de construcción del diagrama de Voronoi del punto más lejano es $O(n\log n)$.




\subsection{El algoritmo}
Sean $P$ un conjunto de $n$ puntos en el plano, $L$ una línea recta y $p_L$ el punto de $P$ más lejano a la recta $L$. Supongamos que la estructura de datos descrita en la sección anterior ya fue construida.

Si el Algoritmo~\ref{TestCasoFacil} aplicado a $p_L$ encuentra a $c_L$ dentro de $R(p_L)$, 
entonces terminamos y reportamos al círculo con centro en $c_L$ y radio $d(c_L, p_L)$.
De lo contrario sabemos que $c_L$ pertenece a una arista de $\mathcal{V}(P)$.

Sea $p^*$ el punto de $P$ más lejano a la línea recta $L$ en el semiplano definido por $L$ que contiene a $c_P$, y sea $p_\perp$ la proyección ortogonal de $p^*$ sobre la recta $L$.

Si $L_{\perp}$ es la línea recta perpendicular a $L$ que pasa por $p^*$, entonces
gracias a la Proposición~\ref{Existe L' paralela a L} podemos garantizar que $L_{\perp}\cap R(p^*)\neq \emptyset$.
Sea entonces $s_{0}$ el punto de intersección de la frontera de $R(p^*)$ con $L_{\perp}$, 
esta intersección es única por la Observación~ \ref{Corta en un solo punto a R(p)} y se puede calcular en tiempo logarítmico usando una búsqueda binaria.

Supongamos que $s_0$ yace sobre una arista $e=uv$ del árbol $\mathcal{V}(P)$, tal que la profundidad de $u$ en el árbol es mayor que la de $v$.
Consideremos la trayectoria $\mathcal T_{u} = \{c_P = v_\lambda, \ldots, v_2, v_1 = v, v_0 = u\}$, por el Teorema~\ref{c_L esta en la T_c_M} podemos garantizar que $c_L$ yace sobre una arista de $\mathcal T_{u}$.
Nuestro objetivo entonces será el de hacer una búsqueda binaria por $c_L$ sobre los vértices de $\mathcal T_{u}$.
Dicho de otra forma, buscamos el único punto de intersección entre $\mathcal T_{u}$ y $L$. Procedemos de la siguiente manera.
\pagebreak
\begin{alg}\label{AlgQueryLine}
Algoritmo para encontrar a $c_L$ sobre la trayectoria $\mathcal T_{u}$.
\end{alg}
 \begin{enumerate}
 	\item Sea $x = v_\lambda$ el nodo de partida y sea $i = 1$.
	\item\ Si $x\in L$, entonces $c_L = x$ y el algoritmo termina.
	\item\ Sea $y$ el $i$-ésimo elemento de $B_x$.
	\item\ Si $y\in L$, entonces $c_L = y$ y el algoritmo termina.
	\item\ Si $x$ y $y$ son vértices consecutivos en la trayectoria $\mathcal T_{u}$, entonces\linebreak$c_L = [x,y]\cap L$ y el algoritmo termina.
	\item\ Determinamos si $x$ y $y$ yacen o no del mismo lado de $L$.	
	\item\ Si yacen en lados distintos, entonces $i = i+1$ y regresamos al paso 2.
	\item\ Si yacen del mismo lado, entonces $x=y$, $i=1$ y regresamos al paso 2.
\end{enumerate}


\begin{tma}
El algoritmo \ref{AlgQueryLine} termina en tiempo $O(\log n)$ y encuentra el centro del $P$-círculo de radio mínimo con centro sobre la recta $L$.
\end{tma}
\begin{proof}

Note que en cada ronda del Algoritmo~\ref{AlgQueryLine} se descarta una fracción lineal de los vértices en $\mathcal T_{u}$, por consiguiente podemos garantizar que el número de rondas en toda ejecución es $O(\log n)$.
Es claro entonces que nuestro algoritmo termina en tiempo $O(\log n)$, ya que todos los pasos requieren de tiempo constante.

El algoritmo anterior realiza una búsqueda binaria sobre los vértices de $\mathcal T_{u}$, hasta encontrar ya sea un vértice de $\mathcal T_{u}$ que esté en $L$, en cuyo caso la búsqueda concluye; o dos vértices consecutivos $x,y$ tales que el segmento que los una corte a la recta $L$.
En el segundo caso, gracias al Lema~\ref{InterseccionUnicaConL}, garantizamos que la búsqueda binaria encuentra al único segmento de $\mathcal T_{u}$ que intersecta a $L$ y por el Teorema~\ref{c_L esta en la T_c_M}, concluimos que $c_L=[x,y]\cap L$.
\end{proof}

Una vez encontrado $c_L$ sobre una arista $e=xy$, como $e$ tiene un apuntador a los dos puntos de $P$ cuyas regiones de Voronoi separa, calcular el radio de $C_L$ requiere de tiempo constante.

Recapitulando, el preprocesado de nuestro algoritmo utiliza $O(n\log n)$ tiempo y espacio para generar una estructura de datos sobre $\mathcal{V}(P)$.
Estructura con la cual, dada cualquier recta $L$, podemos encontrar el centro y radio de $C_L$ en tiempo $O(\log n)$. Recordemos que el espacio puede ser mejorado a $O(n)$ si utilizamos la estructura de datos propuesta por Roy, Karmakar, Das y Nandy en~\cite{ConstrainedMinimumEnclosingCircleWithCenterOnAQueryLineSegment}.











